1223F - Stack Exterminable Arrays - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5;
const int mod = 998244853;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int P;
int v[N];
pair<int,int> h[N];
stack <int> stk;
map<pair<int,int>,int> f;
int fastexp[N];
ll solve(int l,int r){
    ll ans = 0;
    int mij = (l + r)/2;
    if(l < mij)ans+=solve(l,mij);
    if(mij + 1 < r)ans+=solve(mij + 1,r);
    //cout<<l<<' '<<r<<'\n';
    f.clear();
    ///l - > mij
    while(!stk.empty())stk.pop();
    int sz = 0,hsh = 0,hsh2 = 0;
    for(int i = mij;i >= l;i--){
        if(!stk.empty() && stk.top() == v[i]){
            sz--;
            hsh = (hsh - 1ll*h[stk.top()].first*fastexp[sz]%mod + mod)%mod;
            hsh2 = (hsh2 - 1ll*h[stk.top()].second*fastexp[sz]%mod + mod)%mod;
            stk.pop();
        }else{
            stk.push(v[i]);
            hsh = (hsh + 1ll*h[stk.top()].first*fastexp[sz]%mod)%mod;
            hsh2 = (hsh2 + 1ll*h[stk.top()].second*fastexp[sz]%mod)%mod;
            sz++;
        }
        //cout<<mij<<' '<<i<<' '<<hsh<<'\n';
        f[{hsh,hsh2}]++;
    }
    ///mij + 1 - > r
    while(!stk.empty())stk.pop();
    sz = 0;hsh = 0;hsh2 = 0;
    for(int i = mij + 1;i <= r;i++){
        if(!stk.empty() && stk.top() == v[i]){
            sz--;
            hsh = (hsh - 1ll*h[stk.top()].first*fastexp[sz]%mod + mod)%mod;
            hsh2 = (hsh2 - 1ll*h[stk.top()].second*fastexp[sz]%mod + mod)%mod;
            stk.pop();
        }else{
            stk.push(v[i]);
            hsh = (hsh + 1ll*h[stk.top()].first*fastexp[sz]%mod)%mod;
            hsh2 = (hsh2 + 1ll*h[stk.top()].second*fastexp[sz]%mod)%mod;
            sz++;
        }
        ans+=f[{hsh,hsh2}];
    }
    return ans;
}
void solve(){
    int n;
    cin>>n;
    for(int i = 0;i < n;i++){
        cin>>v[i];
        v[i]--;
    }
    cout<<solve(0,n - 1)<<'\n';
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    P = rng()%300 + 300;
    fastexp[0] = 1;
    for(int i = 0;i < N;i++){
        h[i] = {rng()%mod,rng()%mod};
        if(i)fastexp[i] = 1ll*fastexp[i - 1]*P%mod;
    }
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}